package main

import (
	"fmt"

	"gitlab.w2gou.cn/xbc/go-lib/util"
)

// color of node
const (
	RED   = 0
	BLACK = 1
)

// Tree is a struct of red-black tree.
type Tree struct {
	root *node
	size int
}

// NewTree creates a new rbtree.
func NewTree() *Tree {
	return &Tree{}
}

func (t *Tree) First() string {
	if t.root != nil {
		return t.root.Key
	}
	return ""
}

// Find finds the node and return its value.
func (t *Tree) Find(key string) interface{} {
	var result interface{}
	if t == nil {
		return result
	}
	n := t.findnode(key)
	if n != nil {
		return n.Value
	}
	return result
}

// FindIt finds the node and return it as an iterator.
func (t *Tree) FindIt(key string) *node {
	if t == nil || t.root == nil {
		return nil
	}
	return t.findnode(key)
}

// Empty checks whether the rbtree is empty.
func (t *Tree) Empty() bool {
	if t == nil || t.root == nil {
		return true
	}
	return false
}

// Iterator creates the rbtree's iterator that points to the minmum node.
func (t *Tree) Iterator() *node {
	if t == nil || t.root == nil {
		return nil
	}
	return minimum(t.root)
}

// Size returns the size of the rbtree.
func (t *Tree) Size() int {
	if t == nil {
		return 0
	}
	return t.size
}

// Clear destroys the rbtree.
func (t *Tree) Clear() {
	if t != nil {
		t.root = nil
		t.size = 0
	}
}

func (t *Tree) DumpKey() string {
	return t.root.dumpKey()
}

// Insert inserts the key-value pair into the rbtree.
func (t *Tree) Insert(key string, value interface{}) {
	t1 := t.findnode(key)

	if t1 != nil {
		t1.Value = value
		return
	}

	x := t.root
	var y *node

	for x != nil {
		//log.Info4("temp", "Insert for", "xnode", x.Key)

		y = x
		if key < x.Key {
			//log.Info4("temp", "Insert <", "x", x.Key)

			x = x.left

		} else {
			//log.Info4("temp", "Insert >", "x", x.Key)

			x = x.right
		}
	}

	z := &node{parent: y, color: RED, Key: key, Value: value}
	t.size++

	if y == nil {
		z.color = BLACK
		t.root = z
		return
	} else if z.Key < y.Key {
		y.left = z
	} else {
		y.right = z
	}
	t.rbInsertFixup(z)
}

func (t *Tree) leftRotate(x *node) {
	//log.Info4("temp", "left Rotate", "x", x.Key)

	y := x.right
	x.right = y.left

	if y.left != nil {
		y.left.parent = x
	}

	y.parent = x.parent

	if x.parent == nil {
		t.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}

	y.left = x
	x.parent = y
}

func (t *Tree) rightRotate(x *node) {
	//log.Info4("temp", "right Rotate", "x", x.Key)

	y := x.left
	x.left = y.right

	if y.right != nil {
		y.right.parent = x
	}

	y.parent = x.parent

	if x.parent == nil {
		t.root = y
	} else if x == x.parent.right {
		x.parent.right = y
	} else {
		x.parent.left = y
	}
	y.right = x
	x.parent = y
}

// findnode finds the node by key and return it, if not exists return nil.
func (t *Tree) findnode(key string) *node {
	x := t.root
	for x != nil {
		if key < x.Key {
			x = x.left
		} else {
			if key == x.Key {
				return x
			}
			x = x.right
		}
	}
	return nil
}

/*
end.txt 内容如下 digraph {k3->k1;k1->k0;k1->k2;k3->k5;k5->k4;k5->k7;k7->k6;k7->k8;k8->k9;}
从文件中加载命令
dot -Tpng -O end.txt
*/

func (t *Tree) DumpPng(filename string) {
	cmd := fmt.Sprintf("digraph {%v}", t.root.dumpDot())

	//cmdfile := fmt.Sprintf("g%v.txt", i)

	util.WriteFile(filename, cmd)
	util.Cmd(".", "dot", "-Tpng", "-O", filename)

}
